package tree.huffmanTree;

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import javax.activation.MailcapCommandMap;
import javax.swing.text.AbstractDocument.BranchElement;

public class HuffmanTreeCode {
	static Map<Byte, String> hashMap = new HashMap<Byte, String>();
	static StringBuilder stringBuilder  = new StringBuilder();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//哈夫曼编码：
		//构建哈夫曼树节点，包括data（byte），weigth（频率），leftNode，rightNode等
		//然后待编译的字符串存放在bytes数组中，并通过map将byte存放在list数组中。
		//构建赫夫曼树
		HuffmanTreeCode huffmanTreeCode = new HuffmanTreeCode();
//		
//		String string = "i like like like java do you like a javat";
//		byte[] bytes = string.getBytes(); 
//		System.out.println(Arrays.toString(bytes)+";长度："+bytes.length);
//		byte[] byte1 = huffmanTreeCode.zip(bytes);
//		System.out.println(Arrays.toString(byte1)+";长度："+byte1.length);
//		
//		byte[] d =  decode(hashMap, byte1);
//		System.out.println(new String(d));
		
		
		//压缩文件
		
//		huffmanTreeCode.zipFile("/Users/wangjia/Desktop/1.jpg", "/Users/wangjia/Desktop/dst.zip");
//		System.out.println("压缩完成！");
		
		//解压文件
		huffmanTreeCode.deZip("/Users/wangjia/Desktop/dst.zip", "/Users/wangjia/Desktop/src.zip");
		System.out.println("解压完成！");

	}
	
	
	
	//压缩文件
	public void zipFile(String srcFile, String dstFile) {
		InputStream is = null;
		OutputStream os = null;
		ObjectOutputStream oos = null;
		
		try{
			is = new FileInputStream(srcFile);
			byte[] b = new byte[is.available()];
			is.read(b);
			byte[] hfmbytes = zip(b);
			
			os = new FileOutputStream(dstFile);
			oos = new ObjectOutputStream(os);
			oos.writeObject(hfmbytes);
			oos.writeObject(hashMap);
			
			
			
		}catch (Exception e) {
			// TODO: handle exception
			System.out.println(e.getMessage());
		}finally {
			try {
				is.close();
				os.close();
				oos.close();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			
		}
	}
	
	//解压文件
	public void deZip(String srcFile, String dstFile ) {
		InputStream is = null;
		ObjectInputStream ois = null;
		OutputStream os = null;
		
		try {
			is = new FileInputStream(srcFile);
			ois = new ObjectInputStream(is);
			byte[] hfmbytes = (byte[]) ois.readObject();
			Map<Byte, String> hfmMap = (Map<Byte, String>) ois.readObject();
			
			byte[] bytes1 = decode(hfmMap, hfmbytes);
			
			os = new FileOutputStream(dstFile);
			os.write(bytes1);
			
			
		} catch (Exception e) {
			// TODO: handle exception
			System.out.println(e.getMessage());
		}finally {
			// TODO: handle finally clause
			try {
				is.close();
				ois.close();
				os.close();
			} catch (Exception e) {
				// TODO: handle exception
				System.out.println(e.getMessage());
			}		
		}
		
	}
	
	
	/**
	 *  将一个byte 转成一个二进制的字符串, 如果看不懂，可以参考我讲的Java基础 二进制的原码，反码，补码
	 * @param b 传入的 byte
	 * @param flag 标志是否需要补高位如果是true ，表示需要补高位，如果是false表示不补, 如果是最后一个字节，无需补高位
	 * @return 是该b 对应的二进制的字符串，（注意是按补码返回）
	 */
	private static String byteToBitString(boolean flag, byte b) {
		//使用变量保存 b
		int temp = b; //将 b 转成 int
		//如果是正数我们还存在补高位
		if(flag) {
			temp |= 256; //按位与 256  1 0000 0000  | 0000 0001 => 1 0000 0001
		}
		String str = Integer.toBinaryString(temp); //返回的是temp对应的二进制的补码
		if(flag) {
			return str.substring(str.length() - 8);
		} else {
			return str;
		}
	}
	
	
	
	//将赫夫曼编码的数据解码
	@SuppressWarnings("unlikely-arg-type")
	public static byte[] decode(Map<Byte, String> hfmMap,byte[] hfmbytes) {
		//1、先得到赫夫曼编码对应的二进制字符串
		StringBuilder stringBuilder = new StringBuilder();
		boolean flage;
		for (int i = 0; i < hfmbytes.length; i++) {
			flage = (i == hfmbytes.length - 1);
			stringBuilder.append(byteToBitString(!flage, hfmbytes[i]));
		}
		
		//2、将赫夫曼哈希表key和value调换位置
		Map<String, Byte> haspMap1 = new HashMap<String, Byte>();
		for (Map.Entry<Byte, String> entry : hfmMap.entrySet()) {
			haspMap1.put(entry.getValue()+"", entry.getKey());
		}
		//3、将二进制的哈夫曼编码用赫夫曼哈希表（key和value已经调换位置）解析
//		byte[] bytes2 = new byte[];
		List<Byte> list = new ArrayList<Byte>();

		for(int i = 0; i < stringBuilder.length();) {
			int count = 1;//指针
			Byte byte1 = null;
			while(true) {
				if(i+count > stringBuilder.length()-1) {
					i += count;
					break;
				}else {
					String key = stringBuilder.substring(i,i+count);
					byte1 = haspMap1.get(key);
					if(byte1 == null) {//还未找到
						count++;
					}else {
						list.add(byte1);	
						i += count;
						break;
					}
				}
				
			}		
		}
		
		byte[] bytes2 = new byte[list.size()];
		for (int i = 0; i < bytes2.length; i++) {
			bytes2[i] = list.get(i);
		}
		return bytes2;
		
	}
		
	
	public byte[] zip(byte[] bytes) {
		//生成哈夫曼树
		ArrayList<HuffmanTreeNode1> list = getList(bytes);
		HuffmanTreeNode1 huffmanTreeNode1 = buildHuffmanTree(list);
		//hfm编码
		hfmCode(huffmanTreeNode1,"",stringBuilder);
//				System.out.println(hashMap);
		
		return zip(bytes, hashMap);
	}
	
	
	//将bytes转化为list
	public ArrayList<HuffmanTreeNode1> getList(byte[] bytes){
		ArrayList<HuffmanTreeNode1> list = new ArrayList<HuffmanTreeNode1>();
		Map<Byte, Integer> hashMap = new HashMap<>();
		Integer lenght;
		for (int i = 0; i < bytes.length; i++) {
			lenght = hashMap.get(bytes[i]);
			
			if(lenght == null) {
				hashMap.put(bytes[i], 1);
			}else {				
				hashMap.put(bytes[i], lenght+1);
			}
		}
		
		for(Map.Entry<Byte, Integer> entry : hashMap.entrySet()) {
			list.add(new HuffmanTreeNode1(entry.getKey(),entry.getValue()));
		}
		return list;
	
	}

	
	//构建哈夫曼树
	public HuffmanTreeNode1 buildHuffmanTree(ArrayList<HuffmanTreeNode1> list) {
		HuffmanTreeNode1 pareNode;
		while(list.size() > 1) {
			
			//排序
			Collections.sort(list);
			//先取出两个最小的元素
		    pareNode = new HuffmanTreeNode1(null, list.get(0).getWeigth()+list.get(1).getWeigth());
			pareNode.setLeftNode(list.get(0));
			pareNode.setRightNode(list.get(1));
			list.remove(0);
			list.remove(0);
			list.add(pareNode);	
		}
		return list.get(0);
	}
	
	//前序遍历
	public void preOrder(HuffmanTreeNode1 node) {
		if(node == null) {
			return;
		}
		node.preOrder();
	}
//	
	
	
	//hfm编码
	public void hfmCode(HuffmanTreeNode1 node, String aString, StringBuilder stringBuilder) {
		StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
		stringBuilder2.append(aString);
		if(node != null) { //如果node == null不处理
			//判断是不是叶子节点
			if(node.getData() == null) {//非叶子节点
				hfmCode(node.getLeftNode(), "0", stringBuilder2);
				hfmCode(node.getRightNode(), "1", stringBuilder2);
			}else {
				hashMap.put(node.getData(), stringBuilder2.toString());
			}	
		}
	}
	
	//数据压缩：将字符串压缩
	public byte[] zip(byte[] bytes, Map<Byte, String> hfmMap) {
		StringBuilder stringBuilder = new StringBuilder();
		for (int i = 0; i < bytes.length; i++) {
			stringBuilder.append(hfmMap.get(bytes[i]));
		}
		//按照8位一个字节进行压缩
		int len = (stringBuilder.length()+7)/8;
		byte[] bytes1 = new byte[len];
		int index = 0;
		for(int i = 0; i < stringBuilder.length(); i += 8) {
			if(i+8 > stringBuilder.length()) {//最后一个字节了（不到8位）
				bytes1[index++] = (byte) Integer.parseInt(stringBuilder.substring(i), 2);				
			}else {
				bytes1[index++] = (byte) Integer.parseInt(stringBuilder.substring(i, i+8), 2);
			}		
		}
		return bytes1;
		
	}
	
	
	
	
	
}
class HuffmanTreeNode1 implements Comparable<HuffmanTreeNode1>{
	private Byte data;
	private Integer weigth;
	private HuffmanTreeNode1 leftNode;
	private HuffmanTreeNode1 rightNode;
	
	public HuffmanTreeNode1(Byte data, int weigth ) {
		this.data = data;
		this.weigth = weigth;		
	}

	public Byte getData() {
		return data;
	}

	public void setData(byte data) {
		this.data = data;
	}

	public int getWeigth() {
		return weigth;
	}

	public void setWeigth(int weigth) {
		this.weigth = weigth;
	}

	public HuffmanTreeNode1 getLeftNode() {
		return leftNode;
	}

	public void setLeftNode(HuffmanTreeNode1 leftNode) {
		this.leftNode = leftNode;
	}

	public HuffmanTreeNode1 getRightNode() {
		return rightNode;
	}

	public void setRightNode(HuffmanTreeNode1 rightNode) {
		this.rightNode = rightNode;
	}

	@Override
	public String toString() {
		return "HuffmanTreeNode1 [data=" + data + ", weigth=" + weigth + "]";
	}
	
	
	//前序遍历
	public void preOrder() {
		System.out.println(this.toString());
		if(this.leftNode != null) {
			this.leftNode.preOrder();
		}
		if(this.rightNode != null) {
			this.rightNode.preOrder();
		}
	}

	@Override
	public int compareTo(HuffmanTreeNode1 o) {
		// TODO Auto-generated method stub
		return this.getWeigth() - o.getWeigth();//升序
	}
	
	
	
}